/*
kmp算法实现
*/

#include <string.h>
#include <stdio.h>
#include <stdlib.h>

// 采用BF算法，查找在目标串sstr中模式串tstr出现的位置，字符串的起始位置从0开始。
// 只要在目标串sstr中找到了第一个模式串tstr，函数就返回。
// 成功返回模式串tstr在目标串sstr中第一次出现的数组下标，失败返回-1。
int index_bf(char sstr[],char tstr[]);

// 根据模式串tstr，计算next数组，字符串的起始位置从0开始。
// void getnext(char *tstr,int *next)
void getnext(char tstr[],int next[]);

// 根据模式串tstr和next数组计算nextval数组，字符串的起始位置从0开始。
// void getnextval(char *tstr,int *next,int *nextval)
void getnextval(char tstr[],int next[],int nextval[]);

// 采用kmp算法，查找在目标串sstr中模式串tstr出现的位置，字符串的起始位置从0开始。
// 只要在目标串sstr中找到了第一个模式串tstr，函数就返回。
// 成功返回模式串tstr在目标串sstr中第一次出现的数组下标，失败返回-1。
// int index_kmp(char *sstr,char *tstr)
int index_kmp(char sstr[],char tstr[]);


// 字符串从零开始

int main (void)
{
    // char ss[]="ababa";
    // int next[strlen(ss)];
    // getnext(ss,next);
    // for(int i=0;i<strlen(ss);i++)
    // {
    //     printf("%d,",next[i]);
    // }
    // putchar('\n');

    char str[]="aaaabbcabbccaa";
    char tstr[]="cabb";
    int t=index_bf(str,tstr);
    if(t!=-1)
    {
        printf("找到字串\n");
        printf("目标串第一次在模式串中出现的位置是:%d\n",t);
    }

    int x=index_kmp(str,tstr);
    if(x!=-1)
        printf("目标串第一次在模式串中出现的位置是:%d\n",x);
    return 0;
}

int index_bf(char sstr[],char tstr[])
{
    if(sstr==NULL || tstr==NULL)
        return -1;
    int i=0,j=0;
    int slen=strlen(sstr);
    int tlen=strlen(tstr);
    while(i<slen && j<tlen)
    {
        if(sstr[i]==tstr[j])
        {
            i++;
            j++;
        }
        else
        {
            i=i-j+1;        // 因为j即为i在原来的基础上移动的距离.这样就可以比较原串的下一个字符
            j=0;        // 目标串回到原点
        }
    }
    if(j>=tlen)
        return i-tlen;
    else
        return -1;
}

void getnext(char tstr[],int next[])
{
    if(tstr==NULL)  return ;
    int len=strlen(tstr);
    if(len==1)  {next[0]=-1;    return;}
    next[0]=-1;         // 这两个是固定的，这里字符串是从0开始的
    next[1]=0;
    if(len<3)
        return;

    for(int i=2;i<len;i++)
    {
        int max_ii=0;
        int j=1;
        for(;j<i;j++)
        {
            char temp1[len],temp2[len];
            memset(temp1,0,sizeof(temp1));
            memset(temp2,0,sizeof(temp2));

            strncpy(temp1,tstr,j);      // 前缀
            strncpy(temp2,tstr+i-j,j);        // 后缀

            // printf("%s\t%s\n",temp1,temp2);

            if(strcmp(temp1,temp2)==0)
                max_ii=j;
        }
        next[i]=max_ii;
    }
    return;
}


int index_kmp(char sstr[],char tstr[])
{
    if(sstr==NULL || tstr==NULL)
        return -1;
    int slen=strlen(sstr),tlen=strlen(tstr);
    int next[tlen];
    getnext(tstr,next);
    int i=0,j=0;
    while(i<slen && j<tlen)
    {
        if(sstr[i]==tstr[j] || j==-1)
        {
            i++;
            j++;
        }
        else
        {
            // i=i-j+1;
            j=next[j];
        }
    }
    if(j>=tlen)
        return i-tlen;
    else
        return -1;
}